package com.easy.carl.algorithm.linkNode;

import com.easy.leetcode.ListNode;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 142. 环形链表 II
 */
public class DetectCycle142 {
    //存入hashmap
    public ListNode detectCycle1(ListNode head) {
        Map<ListNode, ListNode> hashMap = new HashMap();
        while (head != null) {
            if (hashMap.containsKey(head)) {
                return head;
            } else {
                hashMap.put(head, head);
            }
            head = head.next;
        }
        return null;
    }


    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode quick = head;
        while (quick != null && quick.next != null) {
            slow = slow.next;
            quick = quick.next.next;
            //相遇了，说明有环
            if (slow == quick) {
                //找入口
                ListNode index1 = head;
                ListNode index2 = quick;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}
